1. Field of the Invention
The present invention relates to a method and apparatus for coding input data using a low density parity check code, and also to a method and apparatus for decoding a code coded by the coding method or coding apparatus.
2. Description of the Related Art
In recent years, great advances have been achieved in communication technology such as mobile communication and deep space communication and also in broadcast technology such as surface-wave or satellite digital broadcast technology. With advances in those technologies, active research on the coding theory is being performed to achieve better error correction codes and higher decoding efficiency.
The code performance has a theoretical limit known as Shannon limit proposed by C. E. Shannon.
An object of the research of the coding theory is to achieve codes having high performance close to the Shannon limit. In recent years, coding algorithms called turbo coding such as parallel concatenated convolutional coding (PCCC) or serially concatenated convolutional coding (SCCC), which exhibit high performance close to the Shannon limit, have been developed.
While such turbo coding has been developed, low density parity check (LDPC) coding, which has been known for a long time, is now receiving much attention.
The LDPC coding was first proposed by R. G. Gallager in “Low-Density Parity-Check Codes” (M. I. T. Press, Cambridge, Mass., 1963), and rediscovered by researchers such as D. J. C. Mackay in “Good error correcting codes based on very sparse matrices” (submitted to IEEE Trans. Inf. Theory, IT-45, pp.399–431, 1999) and M. G. Luby, M. Mitzenmacher, M. A. Shokrollahi, and D. A. Spielman in “Analysis of low density codes and improved designs using irregular graphs” (available at http://www.icsi.berkeley.edu/{tilde over ( )}luby/).
Recent researches have revealed that the LDPC coding can provide high performance close to the Shannon limit, like the turbo coding, if the code length is long enough. In LDPC codes, the minimum distance is proportional to the word length, and thus low block error rates can be achieved. Another advantage of LDPC coding is that, unlike the turbo coding, substantially no error floor occurs in decoding.
The LDPC coding is described in further detail below. In the following discussion, the LDPC codes are assumed to be binary linear codes, although the LDPC codes are not necessarily needed to be binary linear codes.
The most significant feature of LDPC codes is that a parity check matrix, which defines a LDPC code, is sparse. Herein, a “sparse matrix” refers to a matrix in which a very small number of elements of the total number of elements have a value of 1. Hereinafter, a sparse parity check matrix is denoted by H. FIG. 14 shows an example of a sparse parity check matrix H, in which the Hamming weight of each column is 3 and the Hamming weight of each row is 6.
LDPC codes, defined by such a parity check matrix H in which all rows are equal in Hamming weight and all columns are equal in Hamming weight, are called regular LDPC codes. In contrast, LDPC codes defined by a parity check matrix H in which Hamming weights are not equal for all rows and not equal for all columns are called irregular LDPC codes.
Coding using LDPC codes is performed as follows. First, a generator matrix G is generated on the basis of a parity check matrix H. A codeword is then generated by multiplying a binary information message by the generator matrix G. More specifically, coding is performed by a coding apparatus designed for coding using LDPC codes, as follows. The coding apparatus first calculates a generator matrix G that satisfies GHT=0 wherein HT is the transpose matrix of the parity check matrix H. If the generator matrix G is a k×n matrix, the coding apparatus generates an n-bit codeword by multiplying a k-bit information message by the generator matrix G. The codeword generated by the coding apparatus is transmitted after the codeword is mapped such that bits of “0” are converted to “+1” and bits of “1” are converted to “−1”. The transmitted codeword is received by a decoding apparatus via a particular communication channel.
LDPC codes can be decoded using probabilistic decoding which is a decoding algorithm proposed by Gallager. In the probabilistic decoding algorithm, decoding is performed via belief propagation on a Tanner graph including variable nodes (also called message nodes) and check nodes according to a message passing algorithm. However, in the probabilistic decoding, because messages which are passed among nodes take real numbers, it is required to deal with real-valued probability distributions associated with messages, and thus very difficult analytical operation is required.
To avoid the above problem, Gallager has proposed algorithm A and algorithm B as algorithms of decoding LDPC codes.
In general, decoding of LDPC codes is performed according to a procedure shown in FIG. 15, in which a received value is denoted by Uo(uoi), a message output from a check node is denoted by uj, a message output from a variable node is denoted by vi, wherein messages refers to real numbers indicating, in log likelihood ratio, likelihood that values are equal to 0.
In decoding of a LDPC code, as shown in FIG. 15, if a received value Uo(uoi) is acquired, in step S11, a message uj is set to be 0 and an integer k is set to be 0, wherein the integer k is a counter value indicating the number of times the process is iterated.
In the next step S12 in the decoding of the LDPC code, a message vi is determined from the received value Uo(uoi) by calculating equation (4) described below.
                              v          i                =                              u                          0              ⁢              i                                +                                    ∑                              j                =                1                                            dv                -                1                                      ⁢                          u              j                                                          (        4        )            
A message uj is then determined from the message vi by calculating equation (5) described below.
                              tanh          ⁡                      (                                          u                j                            2                        )                          =                              ∏                          i              =              1                                      dc              -              1                                ⁢                      tan            ⁢                                                  ⁢                          h              ⁡                              (                                                      v                    i                                    2                                )                                                                        (        5        )            
Furthermore, in step S12 in the LDPC decoding process, the integer k is incremented by 1.
In equation (4), dv is a parameter which can be arbitrarily set to indicate the number of 1s in the vertical direction (in columns of the parity check matrix H, and dc in equation (5) is a parameter which can be arbitrarily set to indicate the number of 1s in the horizontal direction (in rows). For example, in the case of a (3, 6) code, dv=3 and dc=6. In the calculations of equations (4) and (5), a message input from an edge to which an output is to be passed is not used as a parameter in the product or the sum, and thus the product and the sum are calculated in ranges whose upper limits are given by dv−1 and dc−1, respectively. In practice, the calculation of equation (5) is performed by producing a table of a function R which defines one output for given two inputs v1 and v2 according to equation (6), and by iteratively applying the function R as shown in equation (7).x=2 tan h−1{tan h(v1/2)tan h(v2/2)}=R(v1, v2)  (6)uj=R(v1,R(v2,R(v3, . . . R(vdc−2, vdc−1))))  (7)
In the next step S13 in the decoding of the LDPC code, it is determined whether the integer k is greater than N.
If it is determined that the integer k is not greater than N, the process returns to step S12. However, if it is determined that the integer k is greater than N, the process proceeds to step S14.
In step S14 in the LDPC decoding process, a message vi, which is to be output as a final decoding result, is determined by calculating equation (8) described below, and the LDPC decoding process is completed.
                              v          i                =                              u                          0              ⁢              i                                +                                    ∑                              j                =                1                            dv                        ⁢                          u              j                                                          (        8        )            
In equation (8), unlike equation (4), the summation is performed for all messages input from connected edges.
For example, in the case of a (3, 6) code, messages are passed among nodes during the LDPC decoding process as shown in FIG. 16. In FIG. 16, at those nodes marked “=”, a calculation is performed in accordance with equation (4), while a calculation is performed in accordance with equation (5) at those nodes marked “+”1. In the algorithm A described above, messages are binarized and exclusive-OR operation is performed on dc−1 input messages at nodes marked “+”. At nodes marked “=”, if dv−1 input messages are all different in bit value for a given received value R, the sign is inverted in the output.
If irregular LDPC codes are used, the performance of LDPC codes can be improved.
In irregular LDPC codes, a parity check matrix is defined by a degree sequence. The degree sequence indicates the distribution of number of 1s included in the parity check matrix.
However, in LDPC codes, dependence of the performance on the degree sequence has not been investigated, and there are no guidelines for optimization of the degree sequence. In other words, there is a possibility that the performance of LDPC codes can be improved by optimizing the degree sequence.
In decoding of LDPC codes, a received value is first quantized. In the quantization of the received value, or in quantization of messages passed among nodes, the performance varies depending on the quantization step size, in particular, when quantization is performed using a small number of bits.
When quantization is performed using a small number of bits, decoding of LDPC codes is generally performed according to a procedure shown in FIG. 17.
That is, as shown in FIG. 17, in the first step S21 in the LDPC decoding process, a received value Uo(uoi) is quantized using a small number of bits, and a message vi is set to be uoi. Furthermore, an integer k, which is a counter value indicating the number of times the process is iterated, is set to 0, For example, in decoding of LDPC codes, when messages are represented by 2 bits, a received value Uo(uoi) is quantized into a value expressed in 3 bits. In the LDPC decoding process, the received value Uo(uoi) quantized into the 3-bit value is quantized into a 2-bit value and used in calculation of the message vi.
In the next step S22 in the decoding of the LDPC code, a message uj is determined from the message vi, and furthermore, by calculating equation (4), the message vi is determined from the received value Uo(uoi) and the calculated message uj. Furthermore, in step S22 in the LDPC decoding process, the integer k is incremented by 1.
In practice, in decoding of the LDPC code, the message uj represented by the small number of bits is determined by preparing a table of a function R which defines one output represented by the small number of bits for given two inputs v1 and v2, and by iteratively applying the function R, as described earlier. When the message vi is determined according to equation (4), the number of bits increases. The message vi with the increased number of bits is quantized into 2 bits.
In the next step S23 in the decoding of the LDPC code, it is determined whether the integer k is greater than N.
If it is determined that the integer k is not greater than N, the process returns to step S22. However, if it is determined that the integer k is greater than N, the process proceeds to step S24.
In step S24 in the LDPC decoding process, a message vi, which is to be output as a final decoding result, is determined and output. Thus, the LDPC decoding process is completed.
In decoding of LDPC codes, the performance varies depending on the quantization step size used in quantization of a received value and messages passed among nodes. Furthermore, in decoding of LDPC codes, the performance also depends on the quantization step size used to determine messages vi according to equation (4).
However, the dependence of the quantization step size on the performance in decoding of LDPC codes has not been investigated, and there are no guidelines for optimization of the quantization step size. In other words, there is a possibility that the performance of LDPC decoding can be improved by optimizing the quantization step size.